package tsVRPTW;

import static tsVRPTW.EvaluateRoute.*;
import static java.lang.Math.*;
import static tsVRPTW.Parameter.*;

public class TS {

	/**
	 * 禁忌搜索 采用插入算子：一条路径中挑选出一个客户节点插入到另一条路径中，以此作为邻域。在邻域中寻找最优值
	 */
	public static void TabuSearch() {

		double Temp1 = 0;
		double Temp2 = 0;

		// 1.初始化两个禁忌表（默认都未被禁忌）数组的值是禁忌步长（禁忌到哪一代为止）
		// 禁忌车辆，禁忌访问点。（禁忌的是一种操作：使用某个车辆的操作，某个访问点插入到某条路径的操作）
		for (int i = 1; i <= VehicleNumber; i++) {
			for (int j = 2; j < CustomerNumber + 1; j++) { // j=1时表示出发仓库
				Tabu[j][i] = 0; // 二维禁忌表（禁忌i车辆派送j访问点）
			}
			TabuCreate[i] = 0; // 一维禁忌表（禁忌产生新的车辆i）
		}

		// 2.迭代禁忌搜索
		int Iteration = 0; // 初始化迭代次数
		while (Iteration < IterMax) {

			// 0. 初始化以下数据
			int BestC = 0; // 客户编号
			int BestR = 0; // 要插入的路径编号
			int BestP = 0; // 客户在路径中的位置
			double BestV = INF; // 局部最优解（本次迭代的最优解）
			int P = 0; // 初始化顾客在其所在路径中的位置

			// 1. 遍历挑选出客户编号，作为变换的客户节点，找出最合适的客户节点编号
			// 进行一次邻域搜索，找到邻域中的局部最优解，以及与其相对性的邻域变换操作
			for (int i = 2; i <= CustomerNumber + 1; i++) {
				// 1.1 找出i客户在其所在路径中的位置P
				for (int j = 1; j < routes[customers[i].R].V.size(); j++) {
					if (routes[customers[i].R].V.get(j).Number == i) {
						P = j;
						break;
					}
				}
				// 1.2 将客户i从原路径中删除
				removenode(customers[i].R, P, i);
				// 1.3 将客户i插入到其他路径中（不能插入到原来的路径中，因为i节点在原来路径中的位置默认为最佳位置）
				for (int j = 1; j <= VehicleNumber; j++) { // 遍历路径
					for (int k = 1; k < routes[j].V.size(); k++) { // 遍历路径中的节点位置
						if (customers[i].R != j) { // 不能回到原来路径中
							// 1.3.1 尝试将客户i插入到j路径的k位置
							addnode(j, k, i);
							// 1.3.2 记录插入前，原路径和插入路径的时间窗违反量
							Temp1 = routes[customers[i].R].SubT; // 原路径
							Temp2 = routes[j].SubT; // 插入路径
							// 1.3.3 更新插入后，原路径和插入路径的时间窗违反量
							routes[customers[i].R].SubT = 0; // 原路径
							UpdateSubT(routes[customers[i].R]);
							routes[j].SubT = 0; // 插入路径
							UpdateSubT(routes[j]);
							// 1.3.4 记录变换后的评价函数值
							double TempV = Calculation(routes);
							// 1.3.5 判断：是否满足藐视准则；已解禁（超出禁忌步长）或未被禁忌
							if (TempV < Ans // 藐视准则（本次搜索的解优于当前的到全局最优解时，使用藐视准则）
									|| (TempV < BestV) && (routes[j].V.size() > 2 && Tabu[i][j] <= Iteration
											|| routes[j].V.size() == 2 && TabuCreate[j] <= Iteration)) {
								if (TempV < BestV) {
									BestV = TempV; // 局部最优总路径长度
									BestC = i; // best customer
									BestR = j; // best route
									BestP = k; // best position
								}
							}
							// 1.3.6 尝试完成，复原到原路径删除后，新路径插入前的状态（便于插入到下一个位置）
							routes[customers[i].R].SubT = Temp1; // 原路径的时间窗违反量
							routes[j].SubT = Temp2; // 插入路径的时间窗违反量
							removenode(j, k, i); // 从路径中删除客户节点i
						}
					}
				}
//				1.4 将取出的客户节点复原（此时一次邻域搜索完成）
				addnode(customers[i].R, P, i);
			}

			// 2. 更新禁忌表（迭代一次，更新一次禁忌表），禁忌邻域搜索得到局部最优解的操作
			// 从当前代数开始，【TabuTenure * 2 + (int) (random() * 10)】代之内不能再进行此操作
			if (routes[BestR].V.size() == 2) { // 更新一维禁忌表（车辆禁忌表）
				TabuCreate[BestR] = Iteration + TabuTenure * 2 + (int) (random() * 10); // 计算禁忌步长的规则
			}
			Tabu[BestC][customers[BestC].R] = Iteration + TabuTenure * 2 + (int) (random() * 10);

//			3. 获取挑选出的客户在其原来路径中的位置P
			for (int i = 1; i < routes[customers[BestC].R].V.size(); i++) {
				if (routes[customers[BestC].R].V.get(i).Number == BestC) {
					P = i;
					break;
				}
			}

//			4. 生成新的总路径规划
			removenode(customers[BestC].R, P, BestC); // 原路径中删除客户BestC
			addnode(BestR, BestP, BestC); // 插入路径中插入客户BestC
//			4.1 更新原路径
			routes[customers[BestC].R].SubT = 0;
			UpdateSubT(routes[customers[BestC].R]); // 原路径的时间窗违反量
//			4.2 更新插入路径
			routes[BestR].SubT = 0;
			UpdateSubT(routes[BestR]); // 插入路径的时间窗违反量
//			4.3 更新客户BestC所属的路径编号
			customers[BestC].R = BestR;

//			5. 如果以上操作得到的解合法，且满优于已知最优解，则更新全局最优解相关数据
			if ((Check(routes) == true) && (BestV < Ans)) {
				for (int i = 1; i <= VehicleNumber; i++) {
					route_Ans[i].Load = routes[i].Load; // 更新负载
					route_Ans[i].V.clear();
					for (int l = 0; l < routes[i].V.size(); l++) {
						route_Ans[i].V.add(routes[i].V.get(l));
					}
				}
				Ans = BestV;
				solution.add(Ans);
			}
			Iteration++;
		}
	}

	/**
	 *	客户节点Cus加入到路径r中的pos位置 并未涉及更改路径的时间窗违反量
	 * 
	 * @param r   routes[r]，路径
	 * @param pos 要插入客户的位置
	 * @param Cus customers[pos]，客户
	 */
	private static void addnode(int r, int pos, int Cus) {
//		更新路径负载量
		routes[r].Load += customers[Cus].Demand;

//		更新该路径的总长度（）
		routes[r].Dis = routes[r].Dis - Graph[routes[r].V.get(pos - 1).Number][routes[r].V.get(pos).Number]
				+ Graph[routes[r].V.get(pos - 1).Number][customers[Cus].Number]
				+ Graph[customers[Cus].Number][routes[r].V.get(pos).Number];

//		更新路径中的节点集合
		routes[r].V.add(pos, new CustomerType(customers[Cus]));

//		更新客户Cus属于哪条路径
//		customers[Cus].R = r;
	}

	/**
	 *	删除节点，将客户节点Cus从路径r中的pos位置删除 并未涉及更改路径的时间窗违反量
	 * 
	 * @param r
	 * @param pos
	 * @param Cus
	 */
	private static void removenode(int r, int pos, int Cus) {
//		更新路径总负载
		routes[r].Load -= customers[Cus].Demand;

//		更新路径总长度
		routes[r].Dis = routes[r].Dis + Graph[routes[r].V.get(pos - 1).Number][routes[r].V.get(pos + 1).Number]
				- Graph[routes[r].V.get(pos - 1).Number][customers[Cus].Number]
				- Graph[customers[Cus].Number][routes[r].V.get(pos + 1).Number];

//		从路径的客户节点集合去掉该客户节点
		routes[r].V.remove(pos);
	}
}
